package com.gem.day11;

import java.util.LinkedList;
import java.util.Scanner;

/**
 * 本类用来演示LinkedList
 * 它也是List接口的实现类,所以和ArrayList一样,具有有序可重复的特点,
 * 不同点在于,LinkedList底层实现是双向链表,增删效率高,查询效率低
 * 
 * @author easonsy
 * 2020年7月31日 上午8:36:03
 */
/**
 * 面试题: 括号匹配
 * 请用户输入任意() [] {} ,通过程序判定括号是否能配对
 * 
 * 配对要求:
 * OK:	[{}]		{[]{}()}
 * NO:  [([)]		{(){[}]}
 */
public class LinkedListDemo {
	public static void main(String[] args) {
		LinkedList<Character> list = new LinkedList<>();
		Scanner scanner = new Scanner(System.in);
		System.out.println("请您输入括号: ");
		String input = scanner.nextLine();
		char[] charArray = input.toCharArray();
		list.add(charArray[0]);
		for (int i = 1; i < charArray.length; i++) {
			if (list.isEmpty()) {
				list.push(charArray[i]);
				continue;
			}
			if (list.peek() == '(' && charArray[i] == ')' || list.peek() == '[' && charArray[i] == ']'
					|| list.peek() == '{' && charArray[i] == '}') {
				list.pop();
			} else {
				list.push(charArray[i]);
			}
		}
		if (list.isEmpty()) {
			System.out.println("匹配成功...");
		} else {
			System.out.println("匹配失败...");
		}
		scanner.close();
	}
}
